/*
  S.M.A.C.K - An operating system kernel
  Copyright (C) 2010,2011 Mattias Holm and Kristian Rietveld
  For licensing and a full list of authors of the kernel, see the files
  COPYING and AUTHORS.
*/

/*
 * Based on code that is 
 * Copyright 2006 Mattias Holm <mattias.holm(at)openorbit.org>
 */

#include <heap.h>

#include <stdbool.h>
#include <assert.h>


void
heap_init(struct heap_t *h)
{
  h->last = 0;
  h->size = HEAP_SIZE;
}

bool
heap_insert(struct heap_t *h, void *entry, uint32_t deadline)
{
  assert(h);

  if (h->last < h->size - 1) {
    h->elements[h->last + 1].entry = entry;
    h->elements[h->last + 1].deadline = deadline;
    h->last ++;
    // bubble up
    int elem_n = h->last;
    int parent_n = elem_n >> 1;
    while (elem_n > 1) {
      if (h->elements[elem_n].deadline < h->elements[parent_n].deadline) {
        struct heap_entry_t tmp = h->elements[elem_n];
        h->elements[elem_n] = h->elements[parent_n];
        h->elements[parent_n] = tmp;
        elem_n = parent_n;
        parent_n = elem_n >> 1;
      } else {
        // cannot bubble up any more, heap order is satisfied
        break;
      }
    }

    return true;
  }

  return false;
}

void
heap_remove(struct heap_t *h)
{
  assert(h);

  if (h->last >= 1) {
    h->elements[1] = h->elements[h->last];
    h->last --;
    // bubble down
    int elem_n = 1;

    while (elem_n < h->last) {
      int left_child_n = elem_n << 1;
      int right_child_n = (elem_n << 1) + 1;
      int correct_child_n;

      if (right_child_n <= h->last) {
        correct_child_n = (h->elements[left_child_n].deadline < h->elements[right_child_n].deadline)    ? left_child_n
                : right_child_n;
      } else if (left_child_n <= h->last) {
        correct_child_n = left_child_n;
      } else {
        // at bottom, cannot bubble down any more
        break;
      }

      // compare parent and child ranks and bubble down parent if child rank is smaller
      if (h->elements[elem_n].deadline > h->elements[correct_child_n].deadline) {
          struct heap_entry_t tmp = h->elements[elem_n];
          h->elements[elem_n] = h->elements[correct_child_n];
          h->elements[correct_child_n] = tmp;
          elem_n = correct_child_n;
      } else {
        // cannot bubble down any more, heap order satisfied
        break;
      }
    }
  }
}

void *
heap_peek(struct heap_t *h)
{
  assert(h);

  if (h->last)
    return h->elements[1].entry;
  else
    return NULL;
}

unsigned int
heap_peek_rank(struct heap_t *h)
{
  assert(h);

  if (h->last)
    return h->elements[1].deadline;
  else
    return 0xffffffff;
}
